package basic.basic_class02;

/**
 * KMP算法：给定两个字符串，查找一个字符串是否包含另一个字符串，如果包含，返回该字符串的起始下标
 */
public class Code_01_KMP {

	// KMP 算法主体
	public static int getIndexOf(String s, String m) {
		// 首先进行边界条件的判断，如果有一个为空，或者s长度小于m， 则一定无法匹配，直接返回-1
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		// 将s和m改造为字符数组
		char[] ss = s.toCharArray();
		char[] ms = m.toCharArray();
		// 创建两个指针进入while循环，si表示s的索引，mi表示m的索引
		int si = 0;
		int mi = 0;
		int[] next = getNextArray(ms);
		// 结束条件是si和mi其中有一个遍历完了整个字符数组
		while (si < ss.length && mi < ms.length) {
			if (ss[si] == ms[mi]) {
				// 决策一：如果当前s和m位置的元素相等，则两个指针均向后面移动
				si++;
				mi++;
			} else if (next[mi] == -1) {
				// 决策二： 如果不相等，且此时m位于字符数组的起始位置，那么直接将s向后移
				si++;
			} else {
				// 决策三； 如果不想等，但此时的m不在起始位置，则s不懂， m调正到next【mi】的位置继续向相面比较
				mi = next[mi];
			}
		}
		// 等到循环结束时，s和m一定有一个已经全部遍历完了，如果时m遍历完了，则找到了m，否则返回-1
		return mi == ms.length ? si - mi : -1;
	}

	// 给定一个字符串的字符数组，返回一个数组表示每个元素之前字符串的最长公共前后缀，0位置默认-1，1位置默认0；
	public static int[] getNextArray(char[] ms) {
		// 如果数组只有一个元素，默认返回-1；
		if (ms.length == 1) {
			return new int[] { -1 };
		}
		// 创建一个数组，默认和原始数组等长，使得每个位置的元素信息都可以知道
		int[] next = new int[ms.length];
		// 初始化0和1位置上的元素
		next[0] = -1;
		next[1] = 0;
		// 给定两个变量pos和cn进入while循环，pos表示当前元素的位置，cn表示当前元素前面一位的元素最长公共前后缀（就是前面那一位的next[pos - 1]）
		int pos = 2;
		int cn = 0;
		while (pos < next.length) {
			if (ms[pos - 1] == ms[cn]) {
				// 如果前面一位元素与前缀的后一位相等，则next【pos】再前一位的cn基础上+1
				next[pos++] = ++cn;
			} else if (cn > 0) {
				// 如果不相等的话，那么cn指向前缀的后面一位，继续进入循环，此处pos没有进行自增操作，还是在原来的位置
				cn = next[cn];   // 如果没有公共前后缀，一直循环至0
			} else {
				// 此处如果cn == 0 ，则表示前一位的最长公共前后缀不存在，而且此时，mas[pos - 1] != ms[cn] ，则此位置的公共前后缀也一定为0
				next[pos++] = 0;
			}
		}
		// 返回结果集next数组
		return next;
	}

	public static void main(String[] args) {
		String str = "abcabcababaccc";
		String match = "ababa";
		System.out.println(getIndexOf(str, match));
	}
}
